package com.cuz.daileetcode;

/**
 * 见 daiLeetCode47
 */
public class Day47 {

    /***
     *
     * 数字转字符串的方法数
     *
     *数字转字符串的方法数，二叉树权重最大值
     */
    static class NumConvertToLetterWays {
        /**
         * 递归
         */
        static class Recursion {
            public static int solution1Recursion(int num) {
                if (num <= 0) {
                    return 0;
                }
                char[] charArray = String.valueOf(num).toCharArray();
                //从第一个字符开始 存在多少种转化方法
                return recursion(charArray, 0);
            }

            /***
             * 递归
             *
             * 从index位置开始 到char数组末尾存在多少种
             * @param charArray char数组
             * @param index 当前位置
             * @return 方法数
             */
            static int recursion(char[] charArray, int index) {
                if (index == charArray.length) {
                    return 1;
                }
                // 0 无法进行转化
                if (charArray[index] == '0') {
                    return 0;
                }
                //将当前字符单独转化 作为一种方法
                //比如 265，可以把2单独转化成 b65 后序再进行转化
                int indexCharSingle = recursion(charArray, index + 1);
                //如果已经是最后一个在字符 那么直接返回当前字符单独转化的方法数
                if (index + 1 == charArray.length) {
                    return indexCharSingle;
                }
                // 如果当前字符 和 后一个字符构成的数字 小于26 那么
                // 还存在一种情况————当前字符和其后面的字符相连进行转化
                // 比如 265 可以2单独转化 也可以26转化成z 再继续转化
                if ((charArray[index] - '0') * 10 + (charArray[index + 1] - '0') < 26) {
                    indexCharSingle += recursion(charArray, index + 2);
                }
                //返回方法数
                return indexCharSingle;
            }
        }

        static class DynamicPrograming {
            static int dynamicPrograming(int num) {
                if (num <= 0) {
                    return 0;
                }
                char[] charArray = String.valueOf(num).toCharArray();
                int len = charArray.length;
                //dp[index] 表示从charArray index开始的字符到charArray结尾结尾一共右多少种转化方法
                int[] dp = new int[len + 1];
                //最后一个字符法道最后一个字符只有一种方式
                //看到这里可能觉得如果最后一个字符是0 到第二个字符是3 比如xxxx30 那么最后一个字符的转化方式应该是0
                //这一部分的逻辑在 for 循环中if进行判断了 如果后序两个字符构成的数组小于27 那么方法数为1 反之0
                //for 循环中if包含了 最后为0的情况了
                dp[len] = 1;
                if (charArray[len - 1] != '0') {
                    dp[len - 1] = 1;
                }
                for (int index = len - 2; index >= 0; index--) {
                    if (charArray[index] != '0') {
                        int curRes = dp[index + 1];
                        // 如果当前字符 和 后一个字符构成的数字 小于26 那么
                        // 还存在一种情况————当前字符和其后面的字符相连进行转化
                        // 比如 265 可以2单独转化 也可以26转化成z 再继续转化
                        if ((charArray[index] - '0') * 10 + (charArray[index + 1] - '0') < 26) {
                            curRes += dp[index + 2];
                        }
                        dp[index] = curRes;
                    }
                }
                return dp[0];
            }
        }

    }


    static class BinaryTreeMaxRouteWeight {
        static class Node {
            int weight;
            Node left;
            Node right;

        }

        /***
         *  从上到下递归
         */
        static int solution1(Node root) {
            if (root == null) {
                return 0;
            }
            int[] maxWeight = {0};
            weightOfCurNodeRoute(root, 0, maxWeight);
            return maxWeight[0];
        }

        /****
         * 到达当前节点的最大权重
         * @param curNode 当前节点
         * @param preWeightSum 之前产生的路径之和
         * @param  maxWeightArray maxWeightArray[0]记录最大权重
         *                        为什么不传int ————java的值传递和引用传递
         * @return 到达当前节点的最大权重
         */
        static void weightOfCurNodeRoute(Node curNode, int preWeightSum, int[] maxWeightArray) {
            if (curNode.left == null && curNode.right == null) {
                maxWeightArray[0] = Math.max(maxWeightArray[0], preWeightSum + curNode.weight);
            }
            if (curNode.right != null) {
                weightOfCurNodeRoute(curNode.right, preWeightSum + curNode.weight, maxWeightArray);
            }
            if (curNode.left != null) {
                weightOfCurNodeRoute(curNode.left, preWeightSum + curNode.weight, maxWeightArray);
            }
        }

        /***
         *从下到上递归——树形dp
         */
        static int solution2(Node root) {
            if (root == null) {
                return 0;
            }
            return process(root);
        }

        public static int process(Node node) {
            //当前节点为叶子节点 那么返回当前节点的 权重
            if (node.left == null && node.right == null) {
                return node.weight;
            }
            //当前节点 子树的权重
            int nextNodeRouteWeight = Integer.MIN_VALUE;
            //左树不为null 权重为左树的权重
            if (node.left != null) {
                nextNodeRouteWeight = process(node.left);
            }
            //和右树权重比较
            if (node.right != null) {
                nextNodeRouteWeight = Math.max(process(node.right), nextNodeRouteWeight);
            }
            //子树权重较大值+自己权重 就是当前节点以下的最大权重
            return nextNodeRouteWeight + node.weight;
        }
    }

}
